Development of encryption technology related to contents distribution over a network or the like attracts a growing interest today. Particularly, a method of securely and efficiently distributing an encryption key for decrypting encrypted contents attracts a special attention. Generally, a mechanism is necessary in which there are n-number (n is a natural number of two or above) of recipients who have valid reception rights with respect to one distributor who distributes encrypted contents, and only the n-number of recipients among an infinite number of interceptors existing on the network can decrypt the encrypted contents. Further, because the number n of recipients who have the valid reception rights varies with time, there is a demand for a mechanism capable of flexibly dealing with a change in a set of recipients.
Furthermore, in the implementation of such a mechanism, the processing load related to generation, holding and distribution of an encryption key, encryption of contents and so on occurs in the distributor, and the processing load related to holding and reception of a decryption key, decryption of contents and so on occurs in the recipient as a matter of course. It is true that the load on encryption distribution costs is relatively decreasing with various recent technological developments such as improvement in the throughput, the storage capacity or the like of an information processing device and improvement in the communication speed of an information transmission path. However, due to a drastic increase in the number of consumers of contents distribution services and a demand for the encryption technology that is secure enough to guard against skilled malicious interceptors, the processing load imposed by encryption distribution increases accordingly.
In such circumstances, as a technique to securely transmit information to a group of recipients arbitrarily selected by a distributor using a broadcast channel, schemes such as the revocation scheme and the broadcast encryption scheme have been proposed. One example of the broadcast encryption scheme is an encryption key distribution scheme which is disclosed in the following non-patent document 1, and a feature of the scheme is that an improvement in a key derivation path is made on the key distribution scheme using the existing hierarchical tree structure. Specifically, this scheme, in which a set of recipients is regarded as being divided into a plurality of subsets, creates a new subset by adding, to a certain subset, a recipient not included in the subset, and as a result of repeating this, creates a chain of subsets, and then derives an encryption key corresponding to each subset along the chain. It is thereby possible to reduce the number of keys to be held by a recipient, the amount of calculations to generate a decryption key and the traffic for key distribution.    [Non-patent document 1] Nuttapong Attrapadung and Hideki Imai, “Subset Incremental Chain Based Broadcast Encryption with Shorter Ciphertext”, The 28th Symposium on Information Theory and Its Applications (SITA2005)